class Solution {
public:
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     * 
     * @param matrix char字符型vector<vector<>> 
     * @param word string字符串 
     * @return bool布尔型
     */
    /*
    就是遍历矩形所有的点，然后从这个点开始往他的4个方向走;
    因为每一个点我们都可以往他的4个方向查找，所以我们可以把它想象为一棵4叉树，就是每个节点有4个子节点
    由于确定好的路径不能倒退，需要一个标记数组，表示原矩阵中元素已经走过了
    */
    bool hasPath(vector<vector<char> >& matrix, string word) {
        // write code here
        if(matrix.size()==0)
            return false;
        //标记矩阵
        vector<vector<bool>> vis(matrix.size(),vector<bool>(matrix[0].size(),false));
        for(int i=0;i<matrix.size();i++)
            for(int j=0;j<matrix[0].size();j++)
            {
                if(dfs(matrix,word,i,j,0,vis)) return true;
            }
        return false;
    }
      bool dfs(vector<vector<char>>&matrix,string word,int i,int j,int id,vector<vector<bool>>&vis)
        {
          if(i<0||i>=matrix.size()||j<0||j>=matrix[0].size()||vis[i][j]==true)
                return false;
          if(matrix[i][j]!=word[id])
              return false;
          if(id==word.size()-1)
              return true;
          vis[i][j]=true;
          int flag=dfs(matrix, word,i+1, j, id+1, vis)||
              dfs(matrix, word,i-1, j, id+1, vis)||
              dfs(matrix, word,i, j+1, id+1, vis)||
              dfs(matrix, word,i, j-1, id+1, vis);
          vis[i][j]=false;
          return flag;
        }
};